#include <iostream>
#include <vector>
#include <string>
using namespace std;


class Solution {
public:
    // 474. 一和零
    // https://leetcode.cn/problems/ones-and-zeroes/
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));

        for (int i = 1; i<=len; ++i)
        {
            int a = 0, b = 0;
            for (auto& ch : strs[i-1])
            {
                if (ch == '0')  ++a;
                else ++b;
            }
            for (int j = m; j>=a; --j)
            {
                for (int k = n; k>=b; --k)
                {
                    dp[j][k] = max(dp[j][k], dp[j-a][k-b] + 1);
                }
            }
        }

        return dp[m][n];
    }

    // 879. 盈利计划
    // https://leetcode.cn/problems/profitable-schemes/
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        static const int MOD = 1e9 + 7;
        int len = group.size();
        vector<vector<int>> dp(n+1, vector<int>(minProfit+1));
        for (int j = 0; j<=n; ++j)
            dp[j][0] = 1;
        
        for (int i = 1; i<=len; ++i)
        {
            for (int j = n; j>=group[i-1]; --j)
            {
                for (int k = 0; k<=minProfit; ++k)
                {
                    dp[j][k] = (dp[j][k] + dp[j-group[i-1]][max(0, k-profit[i-1])]) % MOD;
                }
            }
        }

        return dp[n][minProfit];
    }
};